package answer

//二分法实现，利用扑克牌原理，堆顶指定是有序的
func lengthOfLIS(nums []int) int {
	pile := 0
	top := make([]int, len(nums))
	for i := 0; i < len(nums); i++ {
		num := nums[i]
		left, right := 0, pile
		for left < right {
			mid := (right-left)>>1 + left
			if num <= top[mid] {
				right = mid
			} else if num > top[mid] {
				left = mid + 1
			}
		}
		if left == pile {
			pile++
		}
		top[left] = num
	}
	return pile
}
